import java.util.Deque;
import java.util.LinkedList;

public class SolutionOffer59II {

    int[] queue=new int[10005];
    int l=0,r=0;
    Deque<Integer> max=new LinkedList<>();

    public SolutionOffer59II() {

    }

    public int max_value() {
        if (max.isEmpty()){
            return -1;
        }
        return queue[max.peek()];
    }

    public void push_back(int value) {
        queue[r++]=value;
        while (!max.isEmpty() && value>=queue[max.getLast()]){
            max.removeLast();
        }
        max.offer(r-1);
    }

    public int pop_front() {
        if (max.isEmpty()){
            return -1;
        }
        while (!max.isEmpty() && max.peek() <= l){
            max.poll();
        }
        return queue[l++];
    }

    public static void main(String[] args) {
        SolutionOffer59II solutionOffer59II=new SolutionOffer59II();
        solutionOffer59II.push_back(1);
        solutionOffer59II.push_back(2);
        System.out.println(solutionOffer59II.max_value());
        solutionOffer59II.push_back(3);
        solutionOffer59II.push_back(0);
        System.out.println(solutionOffer59II.pop_front());
        System.out.println(solutionOffer59II.max_value());
    }
}
